package com.leo.basic.chapter04;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 *
 * @author xuexiaolei
 * @version 2017年12月01日
 */
public class Graph {
    private Node rootNode;//根节点
    private List<Node> nodes = new ArrayList();//所有节点
    private int[][] adjMatrix;//邻接矩阵来保存图的信息

    /**
     * 添加节点
     * @param n
     */
    public void addNode(Node n){
        nodes.add(n);
    }

    /**
     * 默认双向连接这两个节点
     *      扩展：单项连接怎么连？如果有权值的话怎么连？
     * @param start
     * @param end
     */
    public void connectNodes(Node start, Node end){
        if (adjMatrix == null){
            adjMatrix = new int[nodes.size()][nodes.size()];
        }

        int startIndex = nodes.indexOf(start);
        int endIndex = nodes.indexOf(end);
        adjMatrix[startIndex][endIndex]=1;
        adjMatrix[endIndex][startIndex]=1;
    }

    /**
     * 获取节点n的未访问节点
     * @param n     返回第一个相连且未被访问的节点，其余返回null
     * @return
     */
    private Node getUnvisitedChildNode(Node n){
        int index = nodes.indexOf(n);
        for (int i = 0; i < nodes.size(); i++) {
            if (adjMatrix[index][i]==1 && !nodes.get(i).isVisited()){
                return nodes.get(i);
            }
        }
        return null;
    }

    /**
     * 清空节点的访问状态
     */
    private void clearNodes(){
        for (int i = 0; i < nodes.size(); i++) {
            nodes.get(i).setVisited(false);
        }
    }

    private void printNode(Node n){
        System.out.print(n.getLabel()+" ");
    }

    /**
     * 深度优先搜索
     */
    public void dfs(){
        List<Node> stack = new LinkedList<>();
        stack.add(rootNode);
        while (!stack.isEmpty()){
            Node n = stack.get(stack.size() - 1);
            if (!n.isVisited()) {
                printNode(n);
                n.setVisited(true);
            }
            Node next = getUnvisitedChildNode(n);
            if (next!=null){
                stack.add(next);
            }else{
                stack.remove(stack.size()-1);
            }
        }
        clearNodes();
    }

    /**
     * 广度优先搜索
     */
    public void bfs(){
        List<Node> queue = new LinkedList<>();
        queue.add(rootNode);
        printNode(rootNode);
        rootNode.setVisited(true);
        while (!queue.isEmpty()){
            Node n = queue.remove(0);
            Node next;
            while ((next = getUnvisitedChildNode(n)) != null){
                printNode(next);
                next.setVisited(true);
                queue.add(next);
            }
        }
        clearNodes();
    }

    //getter & setter
    public Node getRootNode() {
        return rootNode;
    }
    public void setRootNode(Node rootNode) {
        this.rootNode = rootNode;
    }
    public List getNodes() {
        return nodes;
    }
    public void setNodes(List nodes) {
        this.nodes = nodes;
    }
    public int[][] getAdjMatrix() {
        return adjMatrix;
    }
    public void setAdjMatrix(int[][] adjMatrix) {
        this.adjMatrix = adjMatrix;
    }

    /**
     * 图的节点
     */
    public static class Node{
        char label;
        boolean visited = false;
        Node(char c){
            this.label = c;
        }

        public char getLabel() {
            return label;
        }

        public void setLabel(char label) {
            this.label = label;
        }

        public boolean isVisited() {
            return visited;
        }

        public void setVisited(boolean visited) {
            this.visited = visited;
        }
    }

    public static void main(String[] args) {
        //Lets create nodes as given as an example in the article
        Node nA=new Node('A');
        Node nB=new Node('B');
        Node nC=new Node('C');
        Node nD=new Node('D');
        Node nE=new Node('E');
        Node nF=new Node('F');

        //Create the graph, add nodes, create edges between nodes
        Graph g=new Graph();
        g.addNode(nA);
        g.addNode(nB);
        g.addNode(nC);
        g.addNode(nD);
        g.addNode(nE);
        g.addNode(nF);
        g.setRootNode(nA);

        g.connectNodes(nA,nB);
        g.connectNodes(nA,nC);
        g.connectNodes(nA,nD);

        g.connectNodes(nB,nE);
        g.connectNodes(nB,nF);
        g.connectNodes(nC,nF);


        //Perform the traversal of the graph
        System.out.println("DFS Traversal of a tree is ------------->");
        g.dfs();

        System.out.println("\nBFS Traversal of a tree is ------------->");
        g.bfs();
    }
}
